//
// Created by Administrator on 2022/1/26.
//

#ifndef CPP_LEARNING_LEETCODE216_H
#define CPP_LEARNING_LEETCODE216_H
#include <vector>
using namespace std;
#include <math.h>
#include <iostream>
#include <queue>
#include <functional>

class Solution216 {
public:
    // depth 表示递归深度
    void combinationSum3Help(vector<vector<int>>& result,vector<int>& temp, int n, int k, int depth, int curValue, int& sum){
        if(sum > n){
            return;
        }
        if( depth == k-1){
            int left = n - sum;
            if(left > curValue && 1<=left && left <= 9){
                temp.push_back(left);
                result.push_back(temp);
                temp.pop_back();
            }
            return;
        }
        for(int i=curValue+1; i <= 9; i++){
            temp.push_back(i);
            sum += i;
            combinationSum3Help(result, temp, n, k, depth+1,i, sum);
            temp.pop_back();
            sum -= i;
        }
    }

    vector<vector<int>> combinationSum3(int k, int n) {
        vector<vector<int>> result;
        vector<int> temp;
        int sum = 0;
        combinationSum3Help(result, temp, n, k,0,0,sum);
        return result;
    }

};

void test216(){
    Solution216 s;

    s.combinationSum3(3,9);


}

#endif //CPP_LEARNING_LEETCODE977_H
